package com.itcam.recursion;

import java.util.Arrays;

/**
 * @author : Cammy.Wu
 * Description : 插入排序
 */

public class Demo05InsertSort {
    public static void main(String[] args) {
        int[] a = {3, 2, 6, 1, 5, 7, 4};
        insertSort(a, 1, a.length - 1);
        System.out.println(Arrays.toString(a));
    }

    /**
     * 插入排序的递归实现方法。
     *
     * @param a 待排序的整数数组
     * @param low 当前处理的起始索引
     * @param high 当前处理的结束索引
     */
    private static void insertSort(int[] a, int low, int high) {
        // 如果起始索引大于结束索引，说明排序完成，直接返回
        if (low > high) {
            return;
        }
        // 初始化 i 为 low - 1，用于向前查找插入位置
        int i = low - 1;
        // 保存当前要插入的元素
        int t = a[low];
        // 向前查找插入位置，将比 t 大的元素后移
        while (i >= 0 && a[i] > t) {
            a[i + 1] = a[i];
            i--;
        }
        // 如果插入位置不是当前位置，将 t 插入到正确位置
        if (i + 1 != low) {
            a[i + 1] = t;
        }
        // 递归处理下一个元素
        insertSort(a, low + 1, high);
    }

}
